#include<iostream>

using namespace std;

struct TreeNode
{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x)
		:val(x)
		,left(nullptr)
		,right(nullptr)
	{}
	TreeNode(int x,TreeNode* l,TreeNode* r)
		:val(x)
		,left(l)
		,right(r)
	{}
};

class Solution 
{
public:
	int deep(TreeNode* root)
	{
		if (!root)
			return 0;

		int left = deep(root->left);
		int right = deep(root->right);

		return (left > right) ? left + 1 : right + 1;
	}

    bool IsBalanced_Solution(TreeNode* pRoot) 
    {
		if (!pRoot)
			return true;
		int left = deep(pRoot->left);
		int right = deep(pRoot->right);

		if (abs(left - right) > 1)
		{
			return false;
		}

		return IsBalanced_Solution(pRoot->left) && 
			IsBalanced_Solution(pRoot->right);
    }
};

int main()
{
	TreeNode* F = new TreeNode(7);
	TreeNode* E = new TreeNode(6);
	TreeNode* D = new TreeNode(5);
	TreeNode* C = new TreeNode(4);
	TreeNode* B = new TreeNode(3, E, F);
	TreeNode* A = new TreeNode(2, C, D);
	TreeNode* root = new TreeNode(1, A, B);

	Solution xz;
	int n = xz.IsBalanced_Solution(root);
	
	cout << n << endl;
	return 0;
}